\chapter{Grafowe bazy danych}
%\chapterWithAuthor{Grafowe bazy danych}{Krystian Lieber}
\label{chap:grafoweBazy}

\section{Dlaczego grafowe bazy danych  są interesujące?}

Grafowe bazy danych są jednym z przedstawicieli dynamicznie rozwijającej się grupy określanej jako NoSQL (ang.~\mbox{Not Only SQL} -- nie tylko SQL). Określenie NoSQL powstało w~ odpowiedzi na dynamiczny rozwój nierelacyjnych, rozproszonych baz danych, często niezapewniających ACID\footnote{ACID -- zbiór właściwości gwarantujących poprawne przetwarzanie transakcji w bazach danych, {\it atomicity} -- atomowość, {\it consistency} -- spójność, {\it isolation} -- izolacja, {\it durability} -- trwałość}. Głównym powodem rosnącego zainteresowania bazami nierelacyjnymi jest rosnąca ilość danych i wątpliwość czy tradycyjne bazy relacyjne będą wstanie ją wydajnie przetwarzać. 

Kluczową zaletą grafowych baz danych jest przechowywanie danych w przyjaznej formie, dobrze odwzorowującej rzeczywistość. Umieszczanie wielu danych, takich jak powiązania w~społeczności czy sieci dróg można umieścić w~bazie relacyjnej, jednak nie jest to rozwiązanie naturalne i powoduje problemy na późniejszych etapach.

\section{Co wyróżnia GBD?}
Dane tworzące graf można zapisać na wiele różnych sposobów. W szczególności w RBD można zapisać krawędzie jako tabelę łączącą obiekty w relacji wiele-do-wielu. Czy jest to grafowa baza danych? Oczywiście nie. Co zatem sprawia, że bazę danych nazywamy grafową? 

W grafowej bazie danych graf jest natywną metodą przechowywania informacji. Często określa się, iż GBD to taka, która zapewnia sąsiedztwo wolne od indeksów. Intuicyjnie chodzi o to, iż w GBD informacja o sąsiadach wierzchołka jest przechowywana lokalnie, natomiast w RBD następowałoby odwołanie do indeksu, który wskazywałby sąsiedztwo. Zatem w przypadku GBD czas przeszukiwania sąsiedztwa zależy jedynie od ilości sąsiadów wierzchołka, tak w RBD od ilości wszystkich krawędzi.

\section{Struktura danych}
W teorii graf G(V,E) składa się ze zbioru wierzchołków~V i~zbioru krawędzi~E. Wyróżniamy grafy niezorientowane, zorientowane. Przykładem struktury rzeczywistej reprezentowanej przy pomocy grafu nieorientowanego może być  znajomości na portalu społecznościowym, a~zorientowanej np.~subskrypcje w~portalu społecznościowym. 
Graf mieszany składa się z~trzech zbiorów: zbioru wierzchołków V, zbioru krawędzi nieskierowanych~E i~zbioru krawędzi skierowanych A, pozwala zatem na reprezentacje dwóch poprzednich przykładów w jednej strukturze, pod warunkiem, że między dwoma wierzchołkami występuje jedna krawędź. Graf, w którym może wystąpić więcej niż jedna krawędź między wierzchołkami nazywamy multigrafem. Zatem dobrze będzie jeśli do reprezentacji danych użyty zostanie multigraf mieszany, wtedy obie informacje będzie można przechowywać obok siebie. 

Dla ułatwienia każdą krawędź niezorientowaną przedstawimy jako 2 krawędzie zorientowane. Każdy węzeł może reprezentować obiekt innego typu. Każda krawędź może reprezentować inny związek. Jeśli dodamy do tego możliwość przechowywania właściwości w~krawędziach otrzymamy graf właściwości, który intuicyjnie jest rozszerzeniem grafu ważonego o możliwość definiowania wielu wag o różnych nazwach. 

Właściwości grafu:
\begin{itemize}
\item krawędzie skierowane,
\item krawędzie -- związki (różne),
\item wierzchołki -- obiekty (różne),
\item krawędzie i wierzchołki mają właściwości,
\item właściwości -- pary klucz/wartość.
\end{itemize}
Większość grafowych baz danych korzysta z grafów właściwości, niektóre korzystają z nadgrafów. Główną różnicą jest możliwość by krawędź wskazywała na więcej niż jeden wierzchołek.

\section{Szukanie informacji w GBD}

Zapytanie do GBD jest związane z przeszukaniem grafu. Bardzo istotne, szczególnie w odniesieniu do skalowalności, jest lokalność przesukiwania. W przeciwieństwie do RBD nie wyszukiwanie nie jest globalne, jest jedynie przejściem grafu od wskazanego wierzchołka. Zatem kosztowne złaczenie tabel jest realizowane w postaci prostego przejścia między wierzchołkami. 

Dzięki odpowiednim technologią takim jak interfejs Blueprints możliwe jest pisanie zapytań w jeden prosty sposób dla wielu rodzajów GBD. Inne technologie wspierające zapytania do GBD to GraphQL, SPARQL, GQL.

Blueprints są dla GDB odpowiednikiem JDBC. Na Blueprints operują Gremlin, Pipes i~Rexster.

\section{Wydajność}

W celu pokazania wydajności grafowych baz danych często przytacza się przykład testu dla sieci społecznościowej. Test\footnote{http://techcrunch.com/2009/10/27/neo-technology-commercializes-next-generation-graph-based-database/} przeprowadzono przy użyciu neo4j w~2009 roku. Stworzono strukturę sieci społecznościowej w której każda osoba miała 50 znajomych. Dla 1000 osób wygenerowanie listy znajomych dla każdej osoby zajęło: RBD -- 2000ms, GBD -- 2 ms. By pokazać skalowalność zwiększono ilość osób do ponad miliona, czas zapytania do GBD nadal wynosił 2ms.

Kolejny test\footnote{http://markorodriguez.com/2011/02/18/mysql-vs-neo4j-on-a-large-scale-graph-traversal/} dla dużych grafów przeprowadzono przy użyciu miliona wierzchołków i~4~milionów krawędzi.
Przewaga neo4j nad MySQL rośnie wraz ze wzrostem głębokości przeszukiwania. Co szczególnie ciekawe dla głębokości 5 MySQL nie był wstanie ukończyć testu w~trakcie 2h, podczas gdy neo4j uporał się z zadaniem w 14 minut.

\section{Kiedy użyć GBD?}
\begin{enumerate}
\item Kiedy nie jest potrzebna analiza globalna danych.
\item Kiedy graf jest naturalną metodą przedstawienia danych.
\item Kiedy problem jest lokalny w większej strukturze danych.
\end{enumerate}
Przykłady:
\begin{enumerate}
\item Lokalne wyszukiwanie -- kto jest znajomym Jana?
\item Lokalne rekomendacje -- co kupowały osoby które kupowały daną pralkę?
\item Brakujący znajomi -- kto ze znajomych znajomych Jana nie jest jego znajomym?
\item Szukanie eksperta -- dla tagów pytania znajdź, kto stworzył odpowiedzi na pytania o~tych samych tagach.
\end{enumerate}




